package woa.array;

/**
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 * 输入: [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 * 1、必须在原数组上操作，不能拷贝额外的数组。
 * 2、尽量减少操作次数。
 *
 * @author wangpeng
 * @date 2021/11/8
 */
public class MoveZeroesProblem {

    /**
     * 双指针
     *
     * @param nums
     */
    public static void moveZeroes(int[] nums) {
        int i = 0, j = 1;
        while (j < nums.length) {
            if (nums[i] == 0 && nums[j] != 0) {
                nums[i] = nums[j];
                nums[j] = 0;
                i++;
                j++;
                continue;
            }
            if (nums[i] == 0 && nums[j] == 0) {
                j++;
                continue;
            }
            if (nums[i] != 0 && nums[j] != 0) {
                j++;
                i = j;
                continue;
            }
            if (nums[i] != 0 && nums[j] == 0) {
                i = j;
                j++;
            }
        }
    }

    /**
     * 非0前移，最后补0
     *
     * @param nums
     */
    public static void moveZeroes1(int[] nums) {
        int i = 0;
        //非0前移
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] != 0) {
                nums[i] = nums[j];
                i++;
            }
        }
        //从i开始补0
        for (; i < nums.length; i++) {
            nums[i] = 0;
        }
    }

    /**
     * 双指针优化
     * j指向的不等于0，就交换
     *
     * @param nums
     */
    public static void moveZeroes2(int[] nums) {
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] != 0) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i++;
            }
        }

    }

    /**
     * 双指针优化2
     * 使j - i指向第一个0的位置，用于交换
     *
     * @param nums
     */
    public static void moveZeroes3(int[] nums) {
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] == 0) {
                i++;
            } else if (nums[i] == 0) {
                nums[j - i] = nums[j];
                nums[j] = 0;
            }
        }

    }

    public static void main(String[] args) {
        moveZeroes(new int[]{0,1,0,3,12});
    }
}
